#include <iostream>
using namespace std;


void print_array(int arr[],int n){
	for(int i = 0;i < n;i++){
		cout << arr[i] << " ";
	}
	cout << endl;
}
void swap(int arr[],int a,int b){
	int temp = arr[a];
	arr[a] = arr[b];
	arr[b] = temp;
}
// 维护堆的性质
void heapify(int arr[],int n,int i){
	int largest = i;
	int lson = 2 * i + 1;
	int rson = 2 * i + 2;
	if(lson <n && arr[lson] > arr[largest]){
		largest = lson;
	}
	if(rson < n &&arr[rson] > arr[largest]){
		largest = rson;
	}
	if(largest != i){
		swap(arr,largest,i);
		heapify(arr,n,largest);
	}
}


void heap_sort(int arr[],int n){
	//建堆
	for(int i = n / 2 -1;i >=0;i--){
		heapify(arr,n,i);
	}
	// 排序
	for(int i = n-1;i>0;i--){
		swap(arr,i,0);
		heapify(arr,i,0);
	}
}


int main(){
	int arr[] = {2,3,8,1,4,9,10,7,16,14};
	int n = 10;
	print_array(arr,n);
	heap_sort(arr,n);
	print_array(arr,n);
	
	return 0;
}
